Exploration via Structured Triangulation by a Multi-Robot System with Bearing-Only Low-Resolution Sensors

摘要

This paper presents a distributed approach for exploring and triangulating anunknown region using a multi- robot system. The objective is to produce acovering of an unknown workspace by a fixed number of robots such that thecovered region is maximized, solving the Maximum Area Triangulation Problem(MATP). The resulting triangulation is a physical data structure that is acompact representation of the workspace; it contains distributed knowledge ofeach triangle, adjacent triangles, and the dual graph of the workspace.Algorithms can store information in this physical data structure, such as arouting table for robot navigation Our algorithm builds a triangulation in aclosed environment, starting from a single location. It provides coverage witha breadth-first search pattern and completeness guarantees. We show thecomputational and communication requirements to build and maintain thetriangulation and its dual graph are small. Finally, we present a physicalnavigation algorithm that uses the dual graph, and show that the resulting pathlengths are within a constant factor of the shortest-path Euclidean distance.We validate our theoretical results with experiments on triangulating a regionwith a system of low-cost robots. Analysis of the resulting quality of thetriangulation shows that most of the triangles are of high quality, and cover alarge area. Implementation of the triangulation, dual graph, and navigation alluse communication messages of fixed size, and are a practical solution forlarge populations of low-cost robots.